/*
背景
你的弟弟买了一套新的玩具，用这套玩具，他可以组装自己的机器。在玩具中有很多不同尺寸的齿轮，开始的时候他可以直接使用齿轮组装不同转速比的传动装置，但后来他发现有些转速比用已有的齿轮就很难组装出来。他希望你给他编写一个电脑程序，帮助他找到组装传动装置的方法。

譬如，在这个玩具中包含了 6 齿、12 齿和 30 齿的齿轮，而你的弟弟希望搞一个转速比为 5:4 的传动装置。下图就显示了一种可能的方案：

齿轮传动

这个传动方案使用了四个齿轮，第一跟轴上是 30 齿和 12 齿的，第二跟轴上是 6 齿和 12 齿的。转速比可以通过如下公式获得：

(30 / 12) * (6 / 12) = (5 / 2) * (1 / 2) = 5 / 4 = 5:4

然而，使用以上三种齿轮，就没法组装出转速比为 1 : 6 的传动装置。

题目
给定齿轮的大小（齿轮有多少个齿），判断通过这些齿轮能否组成一定的转速比。我们假定每种齿轮的数量都足够多。

输入
输入的第一行是一个数字 n，它表示在玩具中有几种齿轮（1 <= n <= 20）。下一行包含了 n 个数字 c1...cn，以空白符隔开，他们表示了玩具中的 n 种齿轮的大小（5 <= ci <= 100，其中 1 <= i <= n）。你可以假定在玩具中所有齿轮的大小都是最小齿轮大小的倍数。

再下一行有一个整数 m，它表示所需的实现的转速比有多少组，而之后的 m 行中每行都有两个整数 a 和 b，它们表示要实现的转速比为 a : b，其中 1 <= a, b <= 10000。

提示
请了解一下“动态规划”
*/

#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif
#if defined(_WIN32) && !defined(__cplusplus)
#define inline __inline
#endif

#include <stdio.h>
typedef int		BOOL;
#define TRUE	1
#define FALSE	0
typedef unsigned char BYTE;
typedef unsigned short WORD;
#define MAX_GEAR_NUM 20
#define MAX_GEAR_SIZE 100
#define MAX_RATIO_NUM 10000

int GetGCD(int a, int b)    /*自定义函数求两数的最大公约数*/
{
	int  temp;          /*定义整型变量*/
	if (a < b)             /*通过比较求出两个数中的最大值和最小值*/
	{
		temp = a;
		a = b;
		b = temp;
	}						/*设置中间变量进行两数交换*/
	while (b != 0)           /*通过循环求两数的余数，直到余数为0*/
	{
		temp = a % b;
		a = b;              /*变量数值交换*/
		b = temp;
	}
	return a;            /*返回最大公约数到调用函数处*/
}

int main()
{
	int n, m;
	int gears[MAX_GEAR_NUM];
	WORD ratios[MAX_RATIO_NUM] = {0};


	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &gears[i]);
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (gears[i] % gears[j] == 0)
			{
				int temp = gears[i] / gears[j];
				ratios[temp] = temp;
			}
		}
	}

	for (int i = 0; i < MAX_RATIO_NUM; i++)
	{
		for (int j = 0; j < MAX_RATIO_NUM; j++)
		{
			if (ratios[i] != 0 && ratios[j] != 0)
			{
				int product = ratios[i] * ratios[j];
				if (product < MAX_RATIO_NUM)
				{
					ratios[product] = product;
				}
				if (ratios[i] % ratios[j] == 0)
				{
					int temp = ratios[i] / ratios[j];
					ratios[temp] = temp;
				}
				if (ratios[j] % ratios[i] == 0)
				{
					int temp = ratios[j] / ratios[i];
					ratios[temp] = temp;
				}
			}
		}
	}


	scanf("%d", &m);
	for (int i = 0; i < m; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		int gcd = GetGCD(a, b);
		int tempA = a / gcd;
		int tempB = b / gcd;
		BOOL realized = FALSE;

		for (int j = 1; tempA <= MAX_RATIO_NUM && tempB <= MAX_RATIO_NUM; j++)
		{
			if (ratios[tempA] != 0 && ratios[tempB] != 0)
			{
				realized = TRUE;
				break;
			}
			tempA *= j;
			tempB *= j;
		}
		if (realized) printf("Gear ratio %d:%d can be realized.\n", a, b);
		else printf("Gear ratio %d:%d cannot be realized.\n", a, b);
	}
	return 0;
}